The term Array Processor as utilized herein refers to special purpose computers designed to perform large volume arithmetic computations, called "number crunching", on an array of data. In general they operate as a front end to a host mini-computer or main frame, and perform number crunching applications more efficiently than could their general purpose hosts.
This efficiency of operation is attained through a different architecture. The heart of an Array Processor's architecture is the pipelined processor, which can operate on more than one set of data at a time. Thus, in vector complex multiplication, which is accomplished through a series of additions and multiplications, one part of the pipeline can be multiplying two numbers, while another part can be adding two different numbers.
Applications for Array Processors run the gamut from non-destructive testing, in which arrays of ultrasonic detectors listen for the sound of bearing failure at a multitude of points around a rotating machine, to computer assisted tomography in which radiation sensors detect x-rays which have passed through the body. Additionally Array Processors are extremely useful in Fast Fourier Transform processing in which the amount of computation necessary to obtain a transformed set of data is very large.
As illustrated in U.S. Pat. No. 3,875,391 issued Apr. 1, 1975 to Gerald Shapiro et al, a pipeline signal processor is described in which the arithmetic unit of the processor processes data in parallel and in which the arithmetic processor is under the control of a unit which is made to track the parallel processing such that the flow of command signals is time coincident with the processing through the arithmetic unit.
In order to control this Array Processor, a long horizontal instruction set is utilized. A horizontal instruction is an instruction specifying a set of simultaneously-occurring or parallel computations associated with that instructions's execution through the use of a large number of independent control fields read out at one time upon execution of the horizontal instruction.
These fields include, but are not limited to such tasks as specifying: the number of times an instruction is to be repeated; the address of the start of the alternative instruction path when conditional instruction branching may occur; the function(s) that the pipeline arithmetic unit is to perform during the current horizontal instruction time interval; the computation(s) that determine the source(s) of data for the arithmetic pipeline, usually an initialization or an incrementation; and, the computation(s) that determine the destination(s) of data from the arithmetic pipeline.
The objective of having a number of control fields is that a separate, independent logic element can be dedicated to each control field, which logic element does the computations required for the corresponding field. Hence, there is a requirement that the actions of each field in an instruction be independent of the actions of the remaining fields in that same instruction.
Each horizontal instruction is related to another horizontal instruction, and each horizontal instruction field is related to the other horizontal fields, such that when the horizontal instructions are executed, the arithmetic unit and the memory are utilized at close to 100% efficiency. Because of the inter-relation of the horizontal instructions, and their fields, the horizontal instruction set guarantees that the processing accomplished in the arithmetic unit is coordinated with the retrieval and inputting of information to and from the memory. In theory, instruction sequences can be written such that the amount of wasted pipeline computations are no more than 20% of total operating time. However, to write such instruction sequences requires special training and skill due to the requirement for a different, unusual instruction type. Moreover, in order to perform many algorithms a horizontal instruction may have many unused fields.
While normal horizontal instruction sets are difficult to write, the problem becomes even more severe if more efficient use of program memory is required. In horizontal instruction sets, the longest instructions are the pipeline instructions which require a large number of fields (bits). However, for so-called "bookkeeping" instructions, only a few fields (bits) are necessary. In horizontal instruction sets, the instructions are of fixed length. Thus, when writing bookkeeping instructions, there are large numbers of wasted or unused bits.
Heretofore, "coding" has been utilized to reduce the length of the horizontal instruction and thus reduce waste. In order to reduce the length of a horizontal instruction, it has been the practice in the past to attempt to code a full pipeline instruction so as to express the instruction in a reduced number of bits. While this can be done in many cases, the complexity of programming in this manner, with a reduced number of bits, puts a premium on the ingenuity of the programmer. Not only must the programmer be able to write the appropriate instruction in fewer numbers of bits, he also must keep track of the inter-relation between one instruction and another.
Another problem with horizontal instructions is the number of things to be specified and the number of things which must occur simultaneously. Coding has been used in an attempt to reduce the number of things to be specified. While this also results in reduced numbers of bits, the coding puts a further premium on the programmer's skills.
It should be noted as part of the prior art that horizontal instructions of a modified nature were used in a prior Array Processor sponsored by Wright Patterson Air Force Base. In 1977, in a report under contract F33615-76-C-1339, with the Wright-Patterson Air Force Base, while partial buffering was used in an Array Processor to buffer the commands to the arithmetic unit, horizontal instruction sets were in fact necessitated because address computation was accomplished downstream of the buffer. Thus, in the prior work for Wright-Patterson Air Force Base, no vertical instruction sets could be used since each command or instruction had a significant portion of its field dedicated to other control functions, most especially downstream address computation. It should be noted that in this early work the instructions were inter-dependent. As will become apparent, a vertical instruction set, on the other hand, refers to instructions that can be written independent of other instructions.